/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/contains-duplicate-iii
   @Language: C++
   @Datetime: 20-01-09 11:22
   */

// Method 1, Time O(nlogn+nt), Space O(n)
class Solution {
public:
	bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
		multimap<int,int> keyinx;
		for(int i=nums.size(); i--; keyinx.insert({nums[i],i}));
		for(auto i=keyinx.begin(); i!=keyinx.end(); ++i)
			for(auto j=i; ++j!=keyinx.end() && labs((long)(i->first)-j->first)<=t;)
				if (labs((long)(i->second)-j->second)<=k) return true;
		return false;
	}
};

// Method 2, Time O(nlogk+nk), Space O(k)
class Solution {
public:
	bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
		multiset<int> win;
		for(int i=0; i<nums.size(); win.insert(nums[i++])){
			if (i>k) win.erase(win.find(nums[i-k-1]));
			auto low=win.lower_bound(nums[i]);
			if (low!=win.end() && 0L+*low-nums[i]<=t) return true;
			if (low!=win.begin() && 0L+nums[i]-*--low<=t) return true;
		}
		return false;
	}
};
